Question

二分查找的问题，大神请进（返回值是-1，另外好像一次调用方法中只要返回一个值就会自动结束这个方法吗）

问题出在了index<=1上，现在改成index>=1了，然后，当需要寻找一个数组中不存在的数，却没法返回-1





Answer 1

首先你的二分查找算法模型是错的，因为它并没有体现出高位指针与低位指针是否已超过重合点？如果超过时就结束查找。你应该这样写：

Java语言：

     public static void main(String[] args){
		 int array[]={1,2,3,4,5};
		 System.out.println(binarySearch(array, 3));   // print 2
		 System.out.println(binarySearch(array, 100)); // print -1
	 }

	/**
	 * 折半搜索算法
	 * @param array 有序线性数组
	 * @param findValue 要搜索的值
	 * @return 返回目标值所在数组的下标
	 */
	static int binarySearch(int[] array,int findValue){
		int low,high,middle;
		low=0;               // 低位指针位置
		high=array.length-1; // 高位指针位置
		
		while(low<=high){       // 指针是已超过重合点?
			middle=(low+high)/2;// 定位到中间
			if(findValue<array[middle]) high=middle-1;    // 向低位靠拢
			else if(findValue>array[middle]) low=middle+1;// 向高位靠拢
			else return middle; // 找到了
		}
		
		return -1; // 没有找到
	}

C#语言：

      static void Main(string[] args)
      {
             int[] array={1,2,3,4,5};

             Console.WriteLine(BinarySearch(array, 3));  // print 2
             Console.WriteLine(BinarySearch(array, 100));// print -1

            Console.ReadKey(true);
      }

        /// <summary>
        /// 折半搜索算法
        /// </summary>
        /// <param name="array">有序线性数组</param>
        /// <param name="findValue">要搜索的值</param>
        /// <returns>返回目标值所在数组的下标</returns>
        static int BinarySearch(int[] array, int findValue)
        {
            int low, high, middle;
            low = 0;                 // 低位指针位置
            high = array.Length - 1; // 高位指针位置

            while (low <= high)           // 指针是已超过重合点?
            {      
                middle = (low + high) / 2;// 定位到中间
                if (findValue < array[middle]) high = middle - 1;    // 向低位靠拢
                else if (findValue > array[middle]) low = middle + 1;// 向高位靠拢
                else return middle; // 找到了
            }

            return -1; // 没有找到
        }