이분 검색 법 주의사항

 
使用二分查找,必须要满足：
 
存储在数组中(不可以是链表);
 
有序排列
 
 
 
public class BinarySearch{
    public static int BinarySearch(int []  list , int key ){
        int low = 0，high = list.length -1;
        while( low <= high ){                                   // 1
            int mid = low + ((hight - low) / 2) ;   //2
            if(key<list[mid])
                high = mid - 1;       //3
            else if(key==list[mid])
                return mid;
            else 
                low = mid + 1;
        }
        return - low -1;            //4
    }
}
  
  
주의해 야 할 4 시:
  
1. low < = high 가 low < high 로 바 뀌 면 일치 하 는 요 소 를 찾 을 수 있 습 니 다. 예 를 들 어 배열 에 하나의 요소 만 있 을 때.
  
2. 이것 은 최적화 조치 가 되 어야 합 니 다. (low + high) / 2 를 사용 하면 넘 치 는 위험 이 존재 합 니 다. 우 리 는 int 가 16 비트 이 고 가장 큰 값 은 65535 입 니 다. 만약 에 당신 이 정의 한 배열 이 60000 이 고 low 와 high 는 각각 30000, 40000 이 라 고 가정 하면 이들 을 합치 면 넘 쳐 서 마이너스 가 되 고 위의 코드 를 사용 하면 이런 오류 가 발생 하지 않 습 니 다.사실 우 리 는 컴퓨터 안의 가감 승제 가 제한 을 받 기 때문에 넘 치 는 문 제 를 주의해 야 한다.
3. 최근 에 만 든 문 제 는 하 이 = mid - 1 을 하 이 = mid 로 바 꾸 면 안 된다 는 것 이다. 답 은 안 된다 는 것 이다. 배열 {2, 4, 6, 8} 을 고려 하여 더 이상 배열 의 값 1 을 찾 으 면 순환 이 생 긴 다.
  
4. 이것 도 최적화 조치 여야 합 니 다. 찾 을 키 워드 를 찾 지 못 했 을 때 - (- low - 1) 은 삽입 점 입 니 다. 이 위치 에 키 워드 를 삽입 하면 서열 의 질 서 를 유지 할 수 있 습 니 다.설명: 우선 명확 하 게 말하자면 반드시 마이너스 값 을 되 돌려 야 한다. 관건 값 이 서열 안에 있 지 않다 는 것 을 나타 낸다.그런데 돌아 가면 안 돼 요? - low?답: 안 됩 니 다. 키워드 가 low [0] 보다 작 으 면 - 0 도 0 입 니 다. 이것 은 키워드 가 list [0] 와 일치 하 는 것 을 나타 냅 니 다.그래서 좋 은 선택 은 - low - 1 로 돌아 가 는 것 입 니 다. 키워드 가 서열 에 없 는 것 을 설명 할 뿐만 아니 라 어느 위치 에 꽂 아야 하 는 지도 지적 합 니 다.
  
또 하 나 는 서열 이 증가 하 는 지, 감소 하 는 지, 앞 에 if 판단 을 추가 하 는 것 이다.
  
인터넷 에는 2 분 검색 에 관 한 자료 가 많 지만 정리 할 겨를 이 없다. 그의 용법 과 확장, 대 우 는 나중에 하 자. 배 움 에는 끝 이 없다.